/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-11-06
 * Time: 23:25
 */
class Solution11 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int left, int right) {
        if(left > right) {
            return null;
        }

        if(left == right) {
            return lists[left];
        }

        int mid = (left+right) / 2;
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        return mergeTwo(l1,l2);
    }

    public ListNode mergeTwo(ListNode l1,ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        ListNode newHead = new ListNode(0);
        ListNode ret = newHead;

        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                ret.next = l1;
                ret = l1;
                l1 = l1.next;
            } else {
                ret.next = l2;
                ret = l2;
                l2 = l2.next;
            }
        }

        ret.next = l1 != null ? l1 : l2;
        return newHead.next;
    }
}
